/*
913. 猫和老鼠
已解答
困难
相关标签
相关企业
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。
*/

#include <vector>
using namespace std;

class Solution {
    public:
    int catMouseGame(vector<vector<int>> &graph) {
        int num_point = graph.size();  // 获取图的节点数
        int sgraph[num_point][num_point], mgraph[num_point][num_point];  // 两个图：sgraph 记录猫的游戏状态，mgraph 记录鼠标的游戏状态

        // 初始化 sgraph 和 mgraph 的状态
        for (int i = 1; i < num_point; i++) {  // i 从 1 开始，因为位置 0 为洞口
            for (int j = 0; j < num_point; j++) {
                if (j == 0) {  // 如果目标位置是洞口（0），猫和鼠标都无法到达
                    sgraph[i][j] = 1;  // 如果猫来到了洞口，表示猫获胜
                    mgraph[i][j] = 1;  // 如果鼠标来到了洞口，表示鼠标获胜
                } else {
                    if (i == j) {  // 如果猫和鼠标的位置相同，则猫获胜
                        sgraph[i][j] = 2;
                        mgraph[i][j] = 2;
                    } else {  // 否则初始化为无解状态
                        sgraph[i][j] = 0;
                        mgraph[i][j] = 0;
                    }
                }
            }
        }

        int move = 1, all_flag = 1;
        // 游戏状态的更新，直到找到终局状态或无可用的状态进行更新
        while (move > 0 && sgraph[2][1] == 0) {  // 当猫（2）和鼠标（1）都还没获胜时继续
            move = 0;  // 初始化 move 为 0，每次循环检查是否有状态更新
            // 更新 sgraph (猫的状态) 进行判断
            for (int i = 1; i < num_point; i++) {  // 遍历猫的所有位置
                for (int j = 0; j < num_point; j++) {  // 遍历鼠标的所有位置
                    if (sgraph[i][j] == 0) {  // 如果当前状态尚未被计算过
                        all_flag = 1;  // 默认假设可以选择所有动作
                        for (int k : graph[j]) {  // 遍历鼠标可能的下一步
                            if (mgraph[i][k] == 1) {  // 如果鼠标在下一步就能获胜
                                sgraph[i][j] = 1;  // 更新猫的状态为鼠标胜利
                                move = 1;  // 标记有状态变化
                                break;
                            }
                            if (mgraph[i][k] != 2) {  // 如果鼠标的下一步不是猫胜利
                                all_flag = 0;  // 不是必胜路径
                            }
                        }
                        // 如果鼠标的下一步是必败，猫将获胜
                        if (all_flag == 1 && sgraph[i][j] != 1) {
                            sgraph[i][j] = 2;  // 更新为猫的胜利
                            move = 1;
                        }
                    }
                }
            }
            // 更新 mgraph (鼠标的状态) 进行判断
            for (int i = 1; i < num_point; i++) {  // 遍历猫的位置
                for (int j = 0; j < num_point; j++) {  // 遍历鼠标的位置
                    if (mgraph[i][j] == 0) {  // 如果当前状态尚未被计算过
                        all_flag = 1;  // 默认假设可以选择所有动作
                        for (int k : graph[i]) {  // 遍历猫可能的下一步
                            if (k == 0) continue;  // 如果猫移到洞口，跳过
                            if (sgraph[k][j] == 2) {  // 如果猫的下一步会导致猫获胜
                                mgraph[i][j] = 2;  // 更新为猫获胜
                                move = 1;  // 标记有状态变化
                                break;
                            }
                            if (sgraph[k][j] != 1) {  // 如果猫的下一步不是鼠标胜利
                                all_flag = 0;  // 不是必胜路径
                            }
                        }
                        // 如果猫的下一步是必败，鼠标将获胜
                        if (all_flag == 1 && mgraph[i][j] != 2) {
                            mgraph[i][j] = 1;  // 更新为鼠标获胜
                            move = 1;
                        }
                    }
                }
            }
        }
        // 返回猫和鼠标的初始状态，2 表示猫获胜，1 表示鼠标获胜
        return sgraph[2][1];  // 猫（2）和鼠标（1）的状态，2 为猫获胜，1 为鼠标获胜
    }
};